package com.demo.java.OD351_400.OD396;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【最富裕小家庭财富和(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146244305
 */
public class OdMain {
    public static void main(String[] args) {
        // 创建Scanner对象，用于读取输入
        Scanner scanner = new Scanner(System.in);

        // 读取家庭数量N
        int N = scanner.nextInt();

        // 创建一个数组val，用于存储每个家庭的财富值
        int[] val = new int[N + 1];

        // 读取每个家庭的财富值，存入val数组
        for (int i = 1; i <= N; i++) {
            val[i] = scanner.nextInt();
        }

        // 创建一个Map来存储每个家庭的子家庭列表（通过家庭编号的关联）
        Map<Integer, ArrayList<Integer>> mp = new HashMap<>();

        // 读取家庭之间的关系（父母与子女之间的关系）
        for (int i = 0; i < N - 1; i++) {
            int x1 = scanner.nextInt(); // 父亲家庭编号
            int x2 = scanner.nextInt(); // 儿童家庭编号

            // 将x2加入x1的子家庭列表中
            mp.computeIfAbsent(x1, k -> new ArrayList<>()).add(x2);
        }

        // 变量res用来记录最大家庭财富总和
        int res = 0;

        // 遍历所有的父母家庭
        for (Map.Entry<Integer, ArrayList<Integer>> entry : mp.entrySet()) {
            int key = entry.getKey(); // 父母家庭的编号
            int acc = val[key]; // 当前父母家庭的财富值

            // 遍历子家庭，将其财富加到父母家庭财富中
            for (int i : entry.getValue()) {
                acc += val[i];
            }

            // 更新最大财富值
            res = Math.max(res, acc);
        }

        // 输出最大财富值
        System.out.println(res);
    }
}
